#include <cstdlib>
#include <iostream>
#include <vector>
#include <fstream>
#include <math.h>

using namespace std;
const int MAX =10000;

void voisins(int n, int point[][2], vector<int> voisin[], int dmax){
	
	int tmp;
	srand(time(NULL));
	
	for(int i(0); i<n;i++){
	
		point[i][0]=rand()%612;
		point[i][1]=rand()%792;
				
	}
	
	for(int j(0); j<n; j++){
		
		for(int k(0); k<n; k++){
			
			if(j!=k){
			
				tmp=sqrt(pow(point[j][0]-point[k][0], 2)+(pow(point[j][1]-point[k][1],2)));
				//cout<<tmp<<endl;
				if(tmp<=dmax)
					voisin[j].push_back(k);
		
				
		
			}
		}
		
		
		
	}
	
	
	
}



void AffichageGraphique(int n, int point[][2], vector<int> voisin[])       // Cree le fichier Exemple.ps qui affiche
                                                                     // les points et l'arbre de Kruskal.
{	ofstream output;                           
	output.open("Exemple.ps",ios::out);
	output << "%!PS-Adobe-3.0" << endl;
	output << "%%BoundingBox: 0 0 612 792" << endl;
	output << endl;  
	for(int i=0;i<n;i++)
	{	output << point[i][0] << " " << point[i][1] << " 3 0 360 arc" <<endl;
		output << "0 setgray" <<endl;
		output << "fill" <<endl;
		output << "stroke"<<endl;
		output << endl;
	}
	output << endl;
	for(int i=0;i<n-1;i++)
	{	
		for(int j(0); j<voisin[i].size();j++)
		{
			output << point[i][0] << " " << point[i][1] 
			<< " moveto" << endl;
			output << point[voisin[i][j]][0] << " " << point[voisin[i][j]][1] 
			<< " lineto" << endl;
			output << "stroke" << endl;
			output << endl;
		}
	}
}

void affichage(int n, vector<int> voisin[]){
	
	
	
	for(int i(0); i<n; i++){
		
		cout<<"voisins de "<< i<<" : \t"<<endl;
		
		for(int j(0); j<voisin[i].size(); j++){
			
			cout<<" "<<voisin[i][j];
			
		}
		
		cout<<endl;
		
	}
	
	
	
	
}


bool xVu(int dv[], int n)
{

	for(int i(0); i<n; i++)
	{
		if(dv[i]==0)
			return true;
	}

	return false;

}

int minDij(int dv[MAX], int d[MAX], int n)
{
	int dmin=-1;
	int min =-1; 

	for(int i(0); i<n; i++)
	{
		if(dv[i]==0 && d[i]>-1)
		{
			if(dmin==-1)
			{
				dmin=d[i];
				min=i;
			}
			else
			{
				if(d[i]<dmin)
				{
					dmin=d[i];
					min=i;
				}
			}
		}

	}

return min;



}


void dijkstra(int n, vector<int> voisin[], int point[][2], int pere[])
{
	int d[MAX]; 
	int dv[MAX];
	

	for(int i(0); i<n; i++)
	{
		pere[i]=-1;
	}	
	

	for(int i(0); i<n; i++)
	{
		d[i]=-1;
		dv[i]=0;
	}


	pere[0]=0; d[0]=0;
	
int i;

	while(xVu(dv,n))
	{

			i=minDij(dv, d,n);
			if(i==-1)
			{
				break;
			}
			//cout<<&i<<endl;
				dv[i]=1;

				for(int x(0); x<voisin[i].size(); x++)
				{
					double tmp=sqrt(pow(point[i][0]-point[voisin[i][x]][0], 2)+(pow(point[i][1]-point[voisin[i][x]][1],2)));
					//cout<< tmp<<endl;
					if(dv[voisin[i][x]]==0 && ((d[voisin[i][x]] > d[i]+tmp)||(d[voisin[i][x]]==-1)))
					{
						d[voisin[i][x]]=d[i]+tmp;
						pere[voisin[i][x]]=i;
					}

				}
			

		

		
	}


}


int construitArbre(int n, int pere[], int arbre[MAX-1][2])
{
	int buf=0;

	for(int i(0); i<n; i++)
	{
		if(pere[i]!=-1)
		{
			arbre[i][0]=i;
			arbre[i][1]=pere[i];
			buf++;
		}
	}
	
return buf-1;


}


void AffichageGraphique2(int n, int point[][2], int arbre[][2])       // Cree le fichier Exemple.ps qui affiche
                                                                     // les points et l'arbre de Kruskal.
{	ofstream output;                           
 	output.open("Exemple.ps",ios::out);
 	output << "%!PS-Adobe-3.0" << endl;
 	output << "%%BoundingBox: 0 0 612 792" << endl;
 	output << endl;  
 	for(int i=0;i<n;i++)
   	{	output << point[i][0] << " " << point[i][1] << " 3 0 360 arc" <<endl;
   		output << "0 setgray" <<endl;
   		output << "fill" <<endl;
   		output << "stroke"<<endl;
   		output << endl;
   	}	
 	output << endl;
 	for(int i=0;i<n-1;i++)
   	{	output << point[arbre[i][0]][0] << " " << point[arbre[i][0]][1] 
		   << " moveto" << endl;
  		 output << point[arbre[i][1]][0] << " " << point[arbre[i][1]][1] 
		  << " lineto" << endl;
  		 output << "stroke" << endl;
  		 output << endl;
   }
}





int main(){
int n;  //Le nombre de points.
int m;  //Le nombre d aretes.
int dmax; // La distance jusqu'a laquelle on relie deux points.
cout << "Entrer le nombre de points: ";
cin >> n;

cout << "Entrer la distance minimale: ";
cin >> dmax;

vector<int> voisin[MAX];   // Les listes de voisins.          
int point[MAX][2];         // Les coordonnees des points.

//int d[MAX];                // La distance a la racine.
int arbre[MAX-1][2];       // Les aretes de l'arbre de Dijkstra.
int pere[MAX];             // La relation de filiation de l'arbre de Dijkstra.



voisins( n, point,voisin, dmax);

dijkstra(n,voisin,point,pere);
int p=construitArbre(n,pere,arbre);
AffichageGraphique2(n, point,arbre);
// affichage(n,voisin);



return 0;
}
